본문으로 건너뛰기

60059 - 자물쇠와 열쇠

info
  • 문제 보기: 60059 - 자물쇠와 열쇠
  • 소요 시간: 💥1시간 초과
  • 풀이 언어: java
  • 체감 난이도: 4️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

구현


풀이 코드​

info
  • 메모리: 92200 KB
  • 시간: 6 ms
class Solution {
    int n, m;
    int zeros; // number of zeros in lock
    int[][] key, lock;
    int[][] key90, key180, key270;
    int[][][] keyArr;

    public boolean solution(int[][] key, int[][] lock) {
        this.n = lock.length;
        this.m = key.length;
        this.key = key;
        this.lock = lock;
        initKey();
        initZeros();

        // set offset
        for (int yOfs = -m + 1; yOfs < n; ++yOfs) {
            for (int xOfs = -m + 1; xOfs < n; ++xOfs) {
                boolean[] kFail = new boolean[4];
                int[] cnt = new int[4];

                kfor: // offset done -> match key
                for (int k = 0; k < 4; ++k) {
                    for (int ky = 0; ky < m; ++ky) {
                        for (int kx = 0; kx < m; ++kx) {
                            if (kFail[k]) continue;

                            int ly = ky + yOfs;
                            int lx = kx + xOfs;
                            if (ly < 0 || ly >= n || lx < 0 || lx >= n) continue;

                            int kVal = keyArr[k][ky][kx];
                            int lVal = lock[ly][lx];

                            if ((kVal ^ lVal) == 0) { // collide or can't solve all
                                kFail[k] = true;
                                continue kfor;
                            } else if (lVal == 0) { // match: 1 solved
                                ++cnt[k];
                            }
                        }
                    }
                } // end of key match

                for (int i = 0; i < cnt.length; ++i) {
                    if (cnt[i] == zeros && !kFail[i]) return true;
                }
            }
        }

        return false;
    }

    public void initKey() {
        key90 = new int[m][m];
        key180 = new int[m][m];
        key270 = new int[m][m];
        keyArr = new int[][][]{key, key90, key180, key270};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < m; ++j) {
                key90[j][m - i - 1] = key[i][j];
                key180[m - i - 1][m - j - 1] = key[i][j];
                key270[m - j - 1][i] = key[i][j];
            }
        }
    }

    public void initZeros() {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (lock[i][j] == 0) ++zeros;
            }
        }
    }
}

풀이 해설​

2차원 배열로 된 key를 90도씩 회전하거나 한칸씩 이동해서 lock을 맞춰보는 문제이다.

돌기(1)와 홈(0)이 있고, 돌기끼리 부딪히면 안된다는 조건이 있다.

lock의 모든 홈이 맞춰지면 true를 리턴해야 한다.


📌 로직의 개요​

크게 3-step으로 구성된다.

  1. key에 대한 90/180/270도 회전된 모양을 별도로 저장
  2. key와 lock 간의 오프셋 세팅
  3. matching

배열 확장법으로 풀 수 있다는데 그냥 오프셋으로 계산했다.

오프셋 계산 방식이 훨씬 더 빠름 👍

하지만 배열 확장법도 알아둬서 나쁠건 없어보인다. 풀이하기 더 쉬워진다면야...


📌 XOR Check​

자물쇠와 열쇠의 각 대응되는 칸이 잘 맞아떨어지는지는 XOR 연산으로 판단이 가능하다.

당연히 XOR값이 1이 되어야 한다.

그럼 0이 나오는 경우는?

  1. 자물쇠(1), 열쇠(1) --> 돌기끼리 충돌해서 해당 열쇠 세팅은 무효함
  2. 자물쇠(0), 열쇠(0) --> 자물쇠 홈을 채울 수 없으므로 해당 열쇠 세팅은 무효함

요래 될 것이다.

if ((kVal ^ lVal) == 0) { // collide or can't solve all
    kFail[k] = true;
    continue kfor;
}

반대로 1이 나오는 경우도 따져보자.

  1. 자물쇠(1), 열쇠(0) --> 자물쇠 돌기에 안 부딪히고 스무스하게 넘어감
  2. 자물쇠(0), 열쇠(1) --> 자물쇠 홈을 채움 (OK😉)

따라서 2번 케이스는 따로 카운팅해줬다.

else if (lVal == 0) { // match: 1 solved
    ++cnt[k];
}

🔍 key의 true 여부 검사​

사전에 카운팅해둔 총 자물쇠 홈 개수와 매칭된 홈 개수를 비교해서 true를 리턴할지 판단할 수 있다.

다만 홈이 다 채워졌는데 돌기끼리 충돌해서 열쇠가 무효처리되는 경우도 발생 가능하다.

그래서 kFail도 같이 조건에 들어가게 된다.

for (int i = 0; i < cnt.length; ++i) {
    if (cnt[i] == zeros && !kFail[i]) return true;
}

📌 Early continue & Guard clause​

중첩이 심해서 해당 기법으로 가독성을 개선했다.

if (kFail[k]) continue;
if (ly < 0 || ly >= n || lx < 0 || lx >= n) continue;

메모​

  • 오프셋 계산이 헬임 나머지는 무난함
    • 발상은 다 맞았음 근데 오프셋 계산 삑나서 시간 잡아먹음 (익숙해지면 4~50분 풀이 가능할듯)
❌ 이건 왜 오프셋 틀린건지 설명좀요

오프셋과 i, j, ky, kx 사용 부분 외 나머지는 AC 코드와 동일하다.

public boolean solution(int[][] key, int[][] lock) {
    this.n = lock.length;
    this.m = key.length;
    this.key = key;
    this.lock = lock;
    initKey();
    initZeros();
    
    for (int yOfs = m-1; yOfs > -n; --yOfs) {
        for (int xOfs = m-1; xOfs > -n; --xOfs) {
            // match
            boolean[] kFail = new boolean[4];
            int[] cnt = new int[4];
kfor:          for (int k = 0; k < 4; ++k) { // iterate key variations
                for (int i = 0; i < m; ++i) {
                    for (int j = 0; j < m; ++j) {
                        int ky = i + yOfs;
                        int kx = j + xOfs;

                        if (0 <= ky && ky < m && 0 <= kx && kx < m) { // check in-bound
                            if (!kFail[k]) { // try if this key hasn't failed
                                if ((keyArr[k][ky][kx] ^ lock[i][j]) == 0) {
                                    kFail[k] = true; // fail: drop this key
                                    continue kfor;
                                }
                                else if (lock[i][j] == 0) ++cnt[k]; // solved 1 from lock
                            }
                        }
                    }
                }
                System.out.println();
            }
            // match done for current offset setting
            for (int i = 0; i < cnt.length; ++i) {
                if (cnt[i] == zeros && !kFail[i]) return true;
            }
        }
    }
    
    return false;
}